Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
Example 1:
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 Output: true
Example 2:
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20 Output: false
Constraints:
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-109 <= matix[i][j] <= 109- All the integers in each row are sorted in ascending order.
- All the integers in each column are sorted in ascending order.
-109 <= target <= 109
Average Rating: 4.72 (134 votes)
Solution
Approach 1: Brute Force
Intuition
As a baseline, we can search the 2D array the same way we might search an unsorted 1D array -- by examining each element.
Algorithm
The algorithm doesn't really do anything more clever than what is explained
by the intuition; we loop over the array, checking each element in turn. If
we find it, we return true. Otherwise, if we reach the end of the nested
for loop without returning, we return false. The algorithm must return
the correct answer in all cases because we exhaust the entire search space.
Complexity Analysis
-
Time complexity : O(nm)
Becase we perform a constant time operation for each element of an n×m element matrix, the overall time complexity is equal to the size of the matrix.
-
Space complexity : O(1)
The brute force approach does not allocate more additional space than a handful of pointers, so the memory footprint is constant.
Approach 2: Binary Search
Intuition
The fact that the matrix is sorted suggests that there must be some way to use binary search to speed up our algorithm.
Algorithm
First, we ensure that matrix is not null and not empty. Then, if we
iterate over the matrix diagonals, we can maintain an invariant that the
slice of the row and column beginning at the current (row,col) pair is
sorted. Therefore, we can always binary search these row and column slices
for target. We proceed in a logical fashion, iterating over the diagonals,
binary searching the rows and columns until we either run out of diagonals
(meaning we can return False) or find target (meaning we can return
True). The binarySearch function works just like normal binary search,
but is made ugly by the need to search both rows and columns of a
two-dimensional array.
Complexity Analysis
-
Time complexity : O(log(n!))
It's not super obvious how O(log(n!)) time complexity arises from this algorithm, so let's analyze it step-by-step. The asymptotically-largest amount of work performed is in the main loop, which runs for min(m,n) iterations, where m denotes the number of rows and n denotes the number of columns. On each iteration, we perform two binary searches on array slices of length m−i and n−i. Therefore, each iteration of the loop runs in O(log(m−i)+log(n−i)) time, where i denotes the current iteration. We can simplify this to O(2⋅log(n−i))=O(log(n−i)) by seeing that, in the worst case, n≈m. To see why, consider what happens when n≪m (without loss of generality); n will dominate m in the asymptotic analysis. By summing the runtimes of all iterations, we get the following expression:
(1)O(log(n)+log(n−1)+log(n−2)+…+log(1))
Then, we can leverage the log multiplication rule (log(a)+log(b)=log(ab)) to rewrite the complexity as:
(2)O(log(n)+log(n−1)+log(n−2)+…+log(1))=O(log(n⋅(n−1)⋅(n−2)⋅…⋅1))=O(log(1⋅…⋅(n−2)⋅(n−1)⋅n))=O(log(n!))
Because this time complexity is fairly uncommon, it is worth thinking about its relation to the usual analyses. For one, log(n!)=O(nlogn). To see why, recall step 1 from the analysis above; there are n terms, each no greater than log(n). Therefore, the asymptotic runtime is certainly no worse than that of an O(nlogn) algorithm.
-
Space complexity : O(1)
Because our binary search implementation does not literally slice out copies of rows and columns from
matrix, we can avoid allocating greater-than-constant memory.
Approach 3: Divide and Conquer
Intuition
We can partition a sorted two-dimensional matrix into four sorted submatrices,
two of which might contain target and two of which definitely do not.
Algorithm
Because this algorithm operates recursively, its correctness can be asserted via the correctness of its base and recursive cases.
Base Case
For a sorted two-dimensional array, there are two ways to determine in
constant time whether an arbitrary element target can appear in it. First,
if the array has zero area, it contains no elements and therefore cannot
contain target. Second, if target is smaller than the array's smallest
element (found in the top-left corner) or larger than the array's largest
element (found in the bottom-right corner), then it definitely is not
present.
Recursive Case
If the base case conditions have not been met, then the array has positive
area and target could potentially be present. Therefore, we seek along the
matrix's middle column for an index row such that
matrix[row−1][mid]<target<matrix[row][mid] (obviously, if we find
target during this process, we immediately return true). The existing
matrix can be partitioned into four submatrice around this index; the
top-left and bottom-right submatrice cannot contain target (via the
argument outlined in Base Case section), so we can prune them from the
search space. Additionally, the bottom-left and top-right submatrice are
sorted two-dimensional matrices, so we can recursively apply this algorithm
to them.
Complexity Analysis
-
Time complexity : O(nlogn)
First, for ease of analysis, assume that n≈m, as in the analysis of approach 2. Also, assign x=n2=∣matrix∣; this will make the master method easier to apply. Now, let's model the runtime of the divide & conquer approach as a recurrence relation:
T(x)=2⋅T(4x)+x
The first term (2⋅T(4x)) arises from the fact that we recurse on two submatrices of roughly one-quarter size, while x comes from the time spent seeking along a O(n)-length column for the partition point. After binding the master method variables (a=2;b=4;c=0.5) we notice that logba=c. Therefore, this recurrence falls under case 2 of the master method, and the following falls out:
T(x)=O(xc⋅logx)=O(x0.5⋅logx)=O((n2)0.5⋅log(n2))=O(n⋅log(n2))=O(2n⋅logn)=O(n⋅logn)
Extension: what would happen to the complexity if we binary searched for the partition point, rather than used a linear scan?
-
Space complexity : O(logn)
Although this approach does not fundamentally require greater-than-constant addition memory, its use of recursion means that it will use memory proportional to the height of its recursion tree. Because this approach discards half of
matrixon each level of recursion (and makes two recursive calls), the height of the tree is bounded by logn.
Approach 4: Search Space Reduction
Intuition
Because the rows and columns of the matrix are sorted (from left-to-right and top-to-bottom, respectively), we can prune O(m) or O(n) elements when looking at any particular value.
Algorithm
First, we initialize a (row,col) pointer to the bottom-left of the
matrix.[1] Then, until we find target and return true (or the pointer
points to a (row,col) that lies outside of the dimensions of the
matrix), we do the following: if the currently-pointed-to value is larger
than target we can move one row "up". Otherwise, if the
currently-pointed-to value is smaller than target, we can move one column
"right". It is not too tricky to see why doing this will never prune the
correct answer; because the rows are sorted from left-to-right, we know that
every value to the right of the current value is larger. Therefore, if the
current value is already larger than target, we know that every value to
its right will also be too large. A very similar argument can be made for the
columns, so this manner of search will always find target in the matrix (if
it is present).
Check out some sample runs of the algorithm in the animation below:
Complexity Analysis
-
Time complexity : O(n+m)
The key to the time complexity analysis is noticing that, on every iteration (during which we do not return
true) eitherroworcolis is decremented/incremented exactly once. Becauserowcan only be decremented m times andcolcan only be incremented n times before causing thewhileloop to terminate, the loop cannot run for more than n+m iterations. Because all other work is constant, the overall time complexity is linear in the sum of the dimensions of the matrix. -
Space complexity : O(1)
Because this approach only manipulates a few pointers, its memory footprint is constant.
Footnotes
This would work equally well with a pointer initialized to the top-right. Neither of the other two corners would work, as pruning a row/column might prevent us from achieving the correct answer. ↩︎
Last Edit: September 9, 2018 4:21 AM
approach 4 is amazing!!!
Last Edit: September 5, 2018 5:09 AM
Isn't the binary search on the diagonals a bit silly? You can just run binary search on the rows, for each row, and time complexity is still O(n log n). Approach 4 is very cool though
Me after finished the binary search solution: "I am genius!!!"
Me after looking at the solution 4: "I am so noob!!!"
February 1, 2018 6:31 PM
I think vertical meaning is not correct in the solution. I changed it to following:
class Solution(object):
def binary_search(self, matrix, target, start, vertical):
lo = start
hi = len(matrix)-1 if vertical else len(matrix[0])-1
while hi >= lo:
mid = (lo + hi)/2
if not vertical: # searching a row
if matrix[start][mid] < target:
lo = mid + 1
elif matrix[start][mid] > target:
hi = mid - 1
else:
return True
else: # searching a column
if matrix[mid][start] < target:
lo = mid + 1
elif matrix[mid][start] > target:
hi = mid - 1
else:
return True
return False
def searchMatrixBS(self, matrix, target):
# an empty matrix obviously does not contain `target`
if not matrix:
return False
for i in range(min(len(matrix), len(matrix[0]))):
vertical_found = self.binary_search(matrix, target, i, True)
horizontal_found = self.binary_search(matrix, target, i, False)
if vertical_found or horizontal_found:
return True
return False
Last Edit: October 8, 2018 10:39 PM
In Approach 3, Should it be 'searchRec(left, row, mid-1, down)' instead of 'searchRec(left, up, mid-1, down)'?? Otherwise you are recursing the 3/4 area of the original matrix...
can solution 4 be even faster, i.e. O(lg(m)+lg(n)), if use binary search to replace the one-step-by-one-step search?
March 19, 2019 11:30 AM
In Approach 3: Divide and Conquer, the inner while loop can use binary search again, which will make the time complexity as lg(mn)
Last Edit: November 8, 2018 8:58 AM
Thank you for these clear, diverse solutions! Would anyone mind verifying that the time complexity analysis for divide and conquer (sol 3) + binary search case is as follows:
Let x = n * m.
As shown by OP, T(x) = 2T(x/4) + log(x), due to binary search.
As shown by OP, x^(log of 2 base 4) = x^(1/2).
Since x^(1/2) is polynomially larger than log(x) (some discussion here: https://math.stackexchange.com/questions/1614848/meaning-of-polynomially-larger),
T(x) = O(x^(1/2)), by case 1 of master theorm.
Hence, if we substitute x with n * m, we get T = O((nm)^(1/2)), which is at most O(n), where n is larger of n and m.
Another Divide and Conquer. Every time split the matrix into 4 parts. Using binary tree idea search idea in the 2D matrix. The complexity should be O(max(m,n)). Accepted solution as following:
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length<=0 || matrix[0].length <=0)
{
return false;
}
return searchSubMatrix(matrix, target, 0, 0, matrix.length, matrix[0].length);
}
private boolean searchSubMatrix(int[][] matrix, int target, int startR, int startC, int rows,int columns)
{
if(matrix[startR][startC] == target)
{
return true;
}
//the up left is the smallest item and bottom right is the largest one.
if((columns <= 1 && rows <= 1)
|| !((matrix[startR+rows-1][startC + columns-1]>= target)&&(matrix[startR][startC]<=target)))
{
return false;
}
int newRows = rows/2+rows%2;
int newColumns = columns/2+columns%2;
return searchSubMatrix(matrix, target, startR, startC, newRows, newColumns)
|| searchSubMatrix(matrix, target, startR + rows/2, startC, newRows, newColumns)
|| searchSubMatrix(matrix, target, startR + rows/2, startC+columns/2, newRows, newColumns)
|| searchSubMatrix(matrix, target, startR, startC+columns/2, newRows, newColumns);
}
}
#3 Divide and Conquer: it looks like the description (and time analysis) are wrong. The code splits the input matrix into three, not four. The first matrix is double the size: x/2, not x/4. One matrix is dropped..searchRec(left, up, mid-1, down) || searchRec(mid+1, up, right, row-1); Am i missing something?
Also looks like that row iteration can be avoided: even split, check to choose between first two or the 4th matrix .. then would have constant const instead of sqrt(x) factor in each recursion
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 06/01/2021 12:30 | Accepted | 164 ms | 14.7 MB | cpp |
xxxxxxxxxxclass Solution {public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(); int n = matrix[0].size(); int i = 0, j = n-1; while(i<m && j>=0) { if(matrix[i][j] == target) return true; else if(matrix[i][j] > target) j--; else i++; } return false; }};